/**
 * 200 岛屿数量
 *
 * @author kent
 * @date 2021/5/7 16:03
 */
public class NumIslands {
    public static void main(String[] args) {
        // 岛屿图
        char[][] grid = {{'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '1', '1', '0', '1'}};
        // 求岛屿数量
        int i = numIslands(grid);
        System.out.println("岛屿数量：" + i);
    }

    static void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }

//    /**
//     * 求岛屿数量
//     *
//     * @param grid 岛屿图
//     * @return 岛屿数量
//     */
//    public static int numIslands(char[][] grid) {
//        int islandNum = 0;
//        for (int i = 0; i < grid.length - 1; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                if (grid[i][j] == '1') {
//                    infect(grid, i, j);
//                    islandNum++;
//                }
//            }
//        }
//        return islandNum;
//    }
//    /**
//     * 感染函数
//     */
//    public static void infect(char[][] grid, int i, int j) {
//        if (i < 0 || i >= grid.length ||
//                j < 0 || j >= grid[0].length || grid[i][j] != '1') {
//            return;
//        }
//        grid[i][j] = '2';
//        infect(grid, i + 1, j);
//        infect(grid, i - 1, j);
//        infect(grid, i, j + 1);
//        infect(grid, i, j - 1);
//    }
}
